home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1 / Nebula One.iso / Internet / WWW / swish.11 / src / merge.c < prev    next >
C/C++ Source or Header  |  1995-03-13  |  13KB  |  638 lines
  1. /*
  2. ** Copyright (C) 1995, Enterprise Integration Technologies Corp.        
  3. ** All Rights Reserved.
  4. ** Kevin Hughes, kevinh@eit.com 
  5. ** 3/11/94
  6. */
  7.  
  8. #include "swish.h"
  9. #include "merge.h"
  10.  
  11. /* The main merge functions - it accepts three file names.
  12. ** This is a bit hairy. It basically acts as a zipper,
  13. ** zipping up both index files into one.
  14. */
  15.  
  16. void readmerge(file1, file2, outfile)
  17.      char *file1;
  18.      char *file2;
  19.      char *outfile;
  20. {
  21.     int i, j, indexfilenum1, indexfilenum2, result, totalfiles,
  22.         skipwords, skipfiles;
  23.     long limit1, limit2, fileinfo1, fileinfo2, offsetstart;
  24.     char line[MAXSTRLEN];
  25.     struct indexentry *ip1, *ip2, *ip3;
  26.     struct indexentry *buffer1, *buffer2;
  27.     FILE *fp1, *fp2, *fp3;
  28.  
  29.     initindexfilehashlist();
  30.  
  31.     if ((fp1 = fopen(file1, "r")) == NULL) {
  32.         sprintf(errorstr, "Couldn't read the index file \"%s\".",
  33.         file1);
  34.         progerr(errorstr);
  35.     }
  36.     if (!isokindexheader(fp1)) {
  37.         sprintf(errorstr, "\"%s\" has an unknown format.",
  38.         file1);
  39.         progerr(errorstr);
  40.     }
  41.     if ((fp2 = fopen(file2, "r")) == NULL) {
  42.         sprintf(errorstr, "Couldn't read the index file \"%s\".",
  43.         file2);
  44.         progerr(errorstr);
  45.     }
  46.     if (!isokindexheader(fp2)) {
  47.         sprintf(errorstr, "\"%s\" has an unknown format.",
  48.         file2);
  49.         progerr(errorstr);
  50.     }
  51.  
  52.     ip1 = ip2 = ip3 = NULL;
  53.     buffer1 = buffer2 = NULL;
  54.     if (verbose)
  55.         printf("Counting files... ");
  56.     indexfilenum1 = getindexfilenum(fp1);
  57.     indexfilenum2 = getindexfilenum(fp2);
  58.     totalfiles = indexfilenum1 + indexfilenum2;
  59.     if (verbose) {
  60.         printf("%d files.\n", indexfilenum1 + indexfilenum2);
  61.         printf("Reading stopwords...");
  62.     }
  63.     readoffsets(fp1);
  64.     readstopwords(fp1);
  65.     limit1 = offsets[STOPWORDPOS];
  66.     fileinfo1 = offsets[FILELISTPOS];
  67.     readoffsets(fp2);
  68.     readstopwords(fp2);
  69.     limit2 = offsets[STOPWORDPOS];
  70.     fileinfo2 = offsets[FILELISTPOS];
  71.  
  72.     if (verbose)
  73.         printf("\nReading file info...");
  74.     fseek(fp1, fileinfo1, 0);
  75.     for (i = 1; i <= indexfilenum1; i++) {
  76.         fgets(line, MAXSTRLEN, fp1);
  77.         addindexfilelist(i, line, &totalfiles);
  78.     }
  79.     fseek(fp2, fileinfo2, 0);
  80.     for (i = 1; i <= indexfilenum2; i++) {
  81.         fgets(line, MAXSTRLEN, fp2);
  82.         addindexfilelist(i + indexfilenum1, line, &totalfiles);
  83.     }
  84.  
  85.     if ((fp3 = fopen(outfile, "w")) == NULL) {
  86.         sprintf(errorstr,
  87.         "Couldn't write the merged index file \"%s\".",
  88.         outfile);
  89.         progerr(errorstr);
  90.     }
  91.  
  92.     if (verbose)
  93.         printf("\nMerging words... ");
  94.  
  95.     printheader(fp3, outfile, 0, totalfiles);
  96.  
  97.         offsetstart = ftell(fp3);
  98.         for (i = 0; i < MAXCHARS; i++)
  99.                 fprintf(fp3, "%016li", offsets[i]);
  100.         fputc('\n', fp3);
  101.  
  102.     readoffsets(fp1);
  103.     readoffsets(fp2);
  104.  
  105.     for (i = 0; i < MAXCHARS; i++)
  106.         offsets[i] = 0;
  107.  
  108.     skipwords = 0;
  109.     while (1) {
  110.         if (buffer1 == NULL) {
  111.             ip1 = (struct indexentry *) readindexline(fp1, limit1);
  112.             if (ip1 == NULL)
  113.                 break;
  114.             buffer1 = ip1;
  115.         }
  116.         if (buffer2 == NULL) {
  117.             ip2 = (struct indexentry *) readindexline(fp2, limit2);
  118.             if (ip2 == NULL)
  119.                 break;
  120.             addfilenums(ip2, indexfilenum1);
  121.             buffer2 = ip2;
  122.         }
  123.         result = wordcompare(ip1->word, ip2->word);
  124.         if (!result) {
  125.             ip3 = (struct indexentry *) mergeindexentries(ip1, ip2);
  126.             printindexentry(ip3, fp3);
  127.             freeindexentry(ip1);
  128.             freeindexentry(ip2);
  129.             freeindexentry(ip3);
  130.             buffer1 = buffer2 = NULL;
  131.             skipwords++;
  132.         }
  133.         else if (result < 0) {
  134.             printindexentry(ip1, fp3);
  135.             freeindexentry(ip1);
  136.             buffer1 = NULL;
  137.         }
  138.         else {
  139.             printindexentry(ip2, fp3);
  140.             freeindexentry(ip2);
  141.             buffer2 = NULL;
  142.         }
  143.     }
  144.  
  145.     if (verbose) {
  146.         if (skipwords)
  147.             printf("%d redundant word%s.", skipwords,
  148.             (skipwords == 1) ? "" : "s");
  149.         else
  150.             printf("no redundant words.");
  151.     }
  152.  
  153.         printstopwords(fp3);
  154.         fclose(fp3);
  155.  
  156.     if (verbose)
  157.         printf("\nMerging file info... ");
  158.     fp3 = fopen(outfile, "a+");
  159.  
  160.     offsets[FILELISTPOS] = ftell(fp3);
  161.     for (i = j = 1; i <= indexfilenum1 + indexfilenum2; i++)
  162.         if (getmap(i) == j) {
  163.             addtofilehashlist(j++ - 1, ftell(fp3));
  164.             fprintf(fp3, "%s", lookupindexfilenum(i));
  165.         }
  166.  
  167.     skipfiles = (indexfilenum1 + indexfilenum2) - totalfiles;
  168.     if (verbose) {
  169.         if (skipfiles)
  170.             printf("%d redundant file%s.", skipfiles,
  171.             (skipfiles == 1) ? "" : "s");
  172.         else
  173.             printf("no redundant files.");
  174.     }
  175.  
  176.     printfileoffsets(fp3);
  177.  
  178.     fseek(fp3, offsetstart, 0);
  179.         for (i = 0; i < MAXCHARS; i++)
  180.                 fprintf(fp3, "%016li", offsets[i]);
  181.     fclose(fp3);
  182.  
  183.     fclose(fp1);
  184.     fclose(fp2);
  185.  
  186.     if (verbose)
  187.         printf("\nDone.\n");
  188. }
  189.  
  190. /* Gets the number of files in an index file.
  191. */
  192.  
  193. int getindexfilenum(fp)
  194.      FILE *fp;
  195. {
  196.     int i;
  197.     char line[MAXSTRLEN];
  198.  
  199.     readoffsets(fp);
  200.     fseek(fp, offsets[FILELISTPOS], 0);
  201.  
  202.     i = 0;
  203.     while(ftell(fp) != offsets[FILEOFFSETPOS]) {
  204.         fgets(line, MAXSTRLEN, fp);
  205.         i++;
  206.     }
  207.  
  208.     return i;
  209. }
  210.  
  211. /* This adds an offset to the file numbers in a particular
  212. ** result list. For instance, file 1 has file numbers going from
  213. ** 1 to 10, but so does file 2, so I have to add 10 to all the
  214. ** file numbers in file 2 before merging.
  215. */
  216.  
  217. void addfilenums(ip, num)
  218.      struct indexentry *ip;
  219.      int num;
  220. {
  221.     struct result *rp;
  222.  
  223.     rp = ip->result;
  224.     while (rp != NULL) {
  225.         rp->filenum =
  226.         encodefilenum(getmap(decodefilenum(rp->filenum) + num));
  227.         rp = rp->next;
  228.     }
  229. }
  230.  
  231. /* This reads the next line in the index file and puts the results
  232. ** in a result structure.
  233. */
  234.  
  235. struct indexentry *readindexline(fp, limit)
  236.      FILE *fp;
  237.      long limit;
  238. {
  239.         int i, c, x, countnum, rank, filenum, structure;
  240.         char fileword[MAXWORDLEN];
  241.         struct result *rp;
  242.     struct indexentry *ip;
  243.  
  244.         rp = NULL;
  245.  
  246.     if (limit == ftell(fp))
  247.         return NULL;
  248.         for (i = 0; (c = fgetc(fp)) != 0; ) {
  249.                 if (c == ':') {
  250.                         fileword[i] = '\0';
  251.                         break;
  252.                 }
  253.                 else
  254.                         fileword[i++] = c;
  255.         }
  256.  
  257.         countnum = 1;
  258.  
  259.         ungetc(c, fp);
  260.         while ((c = fgetc(fp)) != 0) {
  261.                 x = 0;
  262.                 do {
  263.                         c = fgetc(fp);
  264.                         if (c == 0)
  265.                                 break;
  266.                         x *= 128;
  267.                         x += c & 127;
  268.                 } while (c & 128);
  269.         if (c == 0)
  270.             break;
  271.                 if (x) {
  272.                         if (countnum == 1) {
  273.                                 filenum = x;
  274.                                 countnum++;
  275.                         }
  276.                         else if (countnum == 2) {
  277.                                 rank = x;
  278.                                 countnum++;
  279.                         }
  280.                         else if (countnum == 3) {
  281.                                 structure = x;
  282.                                 rp = (struct result *)
  283.                                 addtoresultlist(rp, filenum,
  284.                 rank, structure);
  285.                 countnum = 1;
  286.                         }
  287.                 }
  288.         }
  289.  
  290.     ip = (struct indexentry *) emalloc(sizeof(struct indexentry));
  291.     ip->word = (char *) mystrdup(fileword);
  292.     ip->result = rp;
  293.  
  294.         return ip;
  295. }
  296.  
  297. /* This puts all the file info into a hash table so that it can
  298. ** be looked up by its pathname and filenumber. This is how
  299. ** we find redundant file information.
  300. */
  301.  
  302. void addindexfilelist(num, info, totalfiles)
  303.      int num;
  304.      char *info;
  305.      int *totalfiles;
  306. {
  307.     int i;
  308.     static int j;
  309.     unsigned hashval;
  310.     char tmpstr[MAXSTRLEN], path[MAXSTRLEN];
  311.     struct indexfileinfo *ip1, *ip2;
  312.  
  313.     strcpy(path, extractpath(info));
  314.  
  315.     i = lookupindexfilepath(path);
  316.     if (i != -1) {
  317.         *totalfiles = *totalfiles - 1;
  318.         remap(num, i);
  319.         return;
  320.     }
  321.  
  322.     remap(num, j + 1);
  323.     j++;
  324.  
  325.     ip1 = (struct indexfileinfo *) emalloc(sizeof(struct indexfileinfo));
  326.     ip1->filenum = num;
  327.     ip1->fileinfo = (char *) mystrdup(info);
  328.     ip1->path = (char *) mystrdup(path);
  329.  
  330.     sprintf(tmpstr, "%d", num);
  331.     hashval = bighash(tmpstr);
  332.     ip1->next = indexfilehashlist[hashval];
  333.     indexfilehashlist[hashval] = ip1;
  334.  
  335.     ip2 = (struct indexfileinfo *) emalloc(sizeof(struct indexfileinfo));
  336.     ip2->filenum = num;
  337.     ip2->fileinfo = (char *) mystrdup(info);
  338.     ip2->path = (char *) mystrdup(path);
  339.  
  340.     hashval = bighash(path);
  341.     ip2->next = indexfilehashlist[hashval];
  342.     indexfilehashlist[hashval] = ip2;
  343. }
  344.  
  345. /* This extracts the pathname information from the file information
  346. ** line as stored in the index file.
  347. */
  348.  
  349. char *extractpath(s)
  350.      char *s;
  351. {
  352.     int i;
  353.     static char path[MAXSTRLEN];
  354.  
  355.     for (i = 0; s[i] && s[i] != '\"'; i++)
  356.         path[i] = s[i];
  357.     path[i - 1] = '\0';
  358.     path[i] = '\0';
  359.  
  360.     return path;
  361. }
  362.  
  363. /* This returns the file information corresponding to a file number.
  364. */
  365.  
  366. char *lookupindexfilenum(num)
  367.      int num;
  368. {
  369.     unsigned hashval;
  370.     char tmpstr[MAXSTRLEN];
  371.     struct indexfileinfo *ip;
  372.  
  373.     sprintf(tmpstr, "%d", num);
  374.     hashval = bighash(tmpstr);
  375.     ip = indexfilehashlist[hashval];
  376.  
  377.     while (ip != NULL) {
  378.         if (ip->filenum == num)
  379.             return ip->fileinfo;
  380.         ip = ip->next;
  381.     }
  382.     return NULL;
  383. }
  384.  
  385. /* This returns the file number corresponding to a pathname.
  386. */
  387.  
  388. int lookupindexfilepath(path)
  389.      char *path;
  390. {
  391.     unsigned hashval;
  392.     struct indexfileinfo *ip;
  393.  
  394.     hashval = bighash(path);
  395.     ip = indexfilehashlist[hashval];
  396.  
  397.     while (ip != NULL) {
  398.         if (!strcmp(ip->path, path))
  399.             return ip->filenum;
  400.         ip = ip->next;
  401.     }
  402.     return -1;
  403. }
  404.  
  405. /* This simply concatenates two information lists that correspond
  406. ** to a word found in both index files.
  407. */
  408.  
  409. struct indexentry *mergeindexentries(ip1, ip2)
  410.      struct indexentry *ip1;
  411.      struct indexentry *ip2;
  412. {
  413.     struct result *newrp, *rp1, *rp2;
  414.     struct indexentry *ep;
  415.  
  416.     rp1 = ip1->result;
  417.     rp2 = ip2->result;
  418.     newrp = NULL;
  419.  
  420.     while (rp1 != NULL) {
  421.         newrp = (struct result *) addtoresultlist(newrp,
  422.         rp1->filenum, rp1->rank, rp1->structure);
  423.         rp1 = rp1->next;
  424.     }
  425.     while (rp2 != NULL) {
  426.         newrp = (struct result *) addtoresultlist(newrp,
  427.         rp2->filenum, rp2->rank, rp2->structure);
  428.         rp2 = rp2->next;
  429.     }
  430.  
  431.     ep = (struct indexentry *) emalloc(sizeof(struct indexentry));
  432.     ep->word = (char *) mystrdup(ip1->word);
  433.     ep->result = newrp;
  434.  
  435.     return ep;
  436. }
  437.  
  438. /* This prints a new word entry into the merged index file,
  439. ** removing redundant file information as it goes along.
  440. */
  441.  
  442. void printindexentry(ip, fp)
  443.      struct indexentry *ip;
  444.      FILE *fp;
  445. {
  446.     int i, num;
  447.     struct result *rp;
  448.  
  449.     for (i = 0; indexchars[i] != '\0'; i++)
  450.         if ((ip->word)[0] == indexchars[i] && !offsets[i])
  451.             offsets[i] = ftell(fp);
  452.     fprintf(fp, "%s:", ip->word);
  453.     initmarkentrylist();
  454.     rp = ip->result;
  455.     while (rp != NULL) {
  456.         num = rp->filenum;
  457.         if (!ismarked(num)) {
  458.             marknum(num);
  459.             compress(num, fp);
  460.             compress(rp->rank, fp);
  461.             compress(rp->structure, fp);
  462.         }
  463.         rp = rp->next;
  464.     }
  465.     fputc(0, fp);
  466. }
  467.  
  468. /* This associates a number with a new number.
  469. ** This function is used to remap file numbers from index
  470. ** files to a new merged index file.
  471. */
  472.  
  473. void remap(oldnum, newnum)
  474.      int oldnum;
  475.      int newnum;
  476. {
  477.     unsigned hashval;
  478.     char tmpstr[MAXSTRLEN];
  479.     struct mapentry *mp;
  480.  
  481.     mp = (struct mapentry *) emalloc(sizeof(struct mapentry));
  482.     mp->oldnum = oldnum;
  483.     mp->newnum = newnum;
  484.  
  485.     sprintf(tmpstr, "%d", oldnum);
  486.     hashval = bighash(tmpstr);
  487.     mp->next = mapentrylist[hashval];
  488.     mapentrylist[hashval] = mp;
  489. }
  490.  
  491. /* This retrieves the number associated with another.
  492. */
  493.  
  494. int getmap(num)
  495.      int num;
  496. {
  497.     unsigned hashval;
  498.     char tmpstr[MAXSTRLEN];
  499.     struct mapentry *mp;
  500.  
  501.     sprintf(tmpstr, "%d", num);
  502.     hashval = bighash(tmpstr);
  503.     mp = mapentrylist[hashval];
  504.  
  505.     while (mp != NULL) {
  506.         if (mp->oldnum == num)
  507.             return mp->newnum;
  508.         mp = mp->next;
  509.     }
  510.     return num;
  511. }
  512.  
  513. /* This marks a number as having been printed.
  514. */
  515.  
  516. void marknum(num)
  517.      int num;
  518. {
  519.     unsigned hashval;
  520.     char tmpstr[MAXSTRLEN];
  521.     struct markentry *mp;
  522.  
  523.     mp = (struct markentry *) emalloc(sizeof(struct markentry));
  524.     mp->num = num;
  525.  
  526.     sprintf(tmpstr, "%d", num);
  527.     hashval = bighash(tmpstr);
  528.     mp->next = markentrylist[hashval];
  529.     markentrylist[hashval] = mp;
  530. }
  531.  
  532. /* Has a number been printed?
  533. */
  534.  
  535. int ismarked(num)
  536.      int num;
  537. {
  538.     unsigned hashval;
  539.     char tmpstr[MAXSTRLEN];
  540.     struct markentry *mp;
  541.  
  542.     sprintf(tmpstr, "%d", num);
  543.     hashval = bighash(tmpstr);
  544.     mp = markentrylist[hashval];
  545.  
  546.     while (mp != NULL) {
  547.         if (mp->num == num)
  548.             return 1;
  549.         mp = mp->next;
  550.     }
  551.     return 0;
  552. }
  553.  
  554. /* Initialize the marking list.
  555. */
  556.  
  557. void initmarkentrylist()
  558. {
  559.     int i;
  560.     struct markentry *mp;
  561.  
  562.     for (i = 0; i < BIGHASHSIZE; i++) {
  563.         mp = markentrylist[i];
  564.         if (mp != NULL)
  565.             free(mp);
  566.         markentrylist[i] = NULL;
  567.     }
  568. }
  569.  
  570. /* Initialize the main file list.
  571. */
  572.  
  573. void initindexfilehashlist()
  574. {
  575.     int i;
  576.     struct indexfileinfo *ip;
  577.  
  578.     for (i = 0; i < BIGHASHSIZE; i++) {
  579.         ip = indexfilehashlist[i];
  580.         if (ip != NULL)
  581.             free(ip);
  582.         indexfilehashlist[i] = NULL;
  583.     }
  584. }
  585.  
  586. /* Frees up used index entries, my best attempt at memory management...
  587. ** I still have bytes leaking elsewhere...
  588. */
  589.  
  590. void freeindexentry(ip)
  591.      struct indexentry *ip;
  592. {
  593.     struct result *rp, *oldp;
  594.  
  595.     free(ip->word);
  596.     rp = ip->result;
  597.     while (rp != NULL) {
  598.         oldp = rp;
  599.         rp = rp->next;
  600.         free(oldp);
  601.     }
  602.     free(ip);
  603. }
  604.  
  605. /* Translates a file number into something that can be compressed.
  606. */
  607.  
  608. int encodefilenum(num)
  609.      int num;
  610. {
  611.     int i, j;
  612.  
  613.     for (i = j = 0; i != num; i++) {
  614.         j++;
  615.         if (!(j % 128))
  616.             j++;
  617.     }
  618.     return j;
  619. }
  620.  
  621. /* Translates a compressed file number into a correct file number.
  622. */
  623.  
  624. int decodefilenum(num)
  625.      int num;
  626. {
  627.         int i, extra;
  628.  
  629.         for (i = 1, extra = 0; i < num; i++)
  630.                 if (!(i % 128)) {
  631.                         extra++;
  632.                         i++;
  633.                 }
  634.         num -= extra;
  635.  
  636.     return num;
  637. }
  638.